package com.code.test.second.greedy;

import java.util.Arrays;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.md
 * <p>
 * 455.分发饼干
 * 力扣题目链接
 * <p>
 * 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
 * <p>
 * 对每个孩子 i，都有一个胃口值  g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
 * <p>
 * 示例  1:
 * <p>
 * 输入: g = [1,2,3], s = [1,1]
 * 输出: 1 解释:你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输出 1。
 * 示例  2:
 * <p>
 * 输入: g = [1,2], s = [1,2,3]
 * 输出: 2
 * 解释:你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2.
 * 提示：
 * <p>
 * 1 <= g.length <= 3 * 10^4
 * 0 <= s.length <= 3 * 10^4
 * 1 <= g[i], s[j] <= 2^31 - 1
 */
public class SCode455 {

    public static void main(String[] args) {
        int[] children = {1, 2, 7, 10};
        int[] scuit = {1, 3, 5, 9};
        System.out.println(findContentChildren2(children, scuit));
    }

    /**
     * 孩子有胃口:g[i]
     * 饼干有尺寸:s[j]
     * 满足胃口只需要:s[j]>=g[i]
     * <p>
     * g=[1,2,3]
     * s=[1,1]
     * 饼干都是1，拿1喂饱了g1，剩下的s1就喂不了g2了
     * 目标是满足越多的孩子越好，输出满足的孩子数量
     * <p>
     * 大饼干应该优先满足胃口大的，满足胃口小的太浪费，所以胃口小的由小饼干来喂
     */

    public static int findContentChildren(int[] children, int[] scuit) {
        Arrays.sort(children);
        Arrays.sort(scuit);

        int start = 0;
        int count = 0;
        /**
         * 这里逻辑是，从小到大遍历饼干，然后看这个饼干能否满足孩子，如果满足了一个孩子，则往下移动
         */
        for (int i = 0; i < scuit.length; i++) {//饼干
            if (scuit[i] >= children[start]) {//如果饼干满足了胃口
                start++;
                count++;
            }
        }
        return count;
    }

    public static int findContentChildren2(int[] children, int[] scuit) {
        Arrays.sort(children);
        Arrays.sort(scuit);

        int start = scuit.length - 1;
        int count = 0;
        /**
         * 这里逻辑是，从小到大遍历饼干，然后看这个饼干能否满足孩子，如果满足了一个孩子，则往下移动
         */
        /**
         * 这里胃口是从大到小的
         */
        for (int i = children.length - 1; i >= 0; i--) {//胃口
            //胃口和饼干数量不一定对等
            if (start >= 0 && scuit[start] >= children[i]) {//如果饼干可以满足这个胃口
                start--;
                count++;
            }
        }
        return count;
    }


}
